1. Field of the Invention
The present invention is directed to controlling network transmissions. More particularly, the present invention relates to classifying data packets in an internetworking environment.
2. Related Art
As network infrastructure is being geared to support newly enhanced services, an evolution in the mechanisms that are used to handle traffic in networks can be observed. Packet switching introduces the task of routing a packet (i.e., IP datagram or protocol data unit (PDU)) based on its destination address. This task was simple in the past, not only because of the low volume of traffic, but also because there was only a need to examine only one dimension (i.e., field) in a packet header. As networks continue to evolve, the task of packet routing will became even more complex with the need for policy-based routing, access-control in networks, traffic accounting and billing, support for quality of service, per-flow computation in active networks, and the like.
All the mechanisms that achieve packet routing today can be categorized broadly into a problem domain called “classification of packets.” The key idea in packet classification is to find a best fit among a set of rules, where each rule describes a class of packets. A subsequent operation is to perform the action associated with the best-fit rule. However, as suggested, several factors render conventional packet classification techniques ineffective. For instance, as the set of rules increases in size, more memory space is required to search and identify the appropriate rule that matches an incoming packet. Additionally, the dimensions of search space for identifying a rule are directly proportional to the number of fields supported in a rule.
Another challenge to efficient packet classification involves the hierarchy of protocol headers. If the data traffic includes multiple patterns of protocol headers (e.g. [Ethernet+IP+TCP], [Ethernet+IP+UDP], and [Ethernet+ARP]), it is imperative to identify the correct pattern of protocol headers before applying the rule-matching function.
Conventional packet classification methodologies are also impaired by frequent rule changes. In other words, the rule set typically changes or is updated during due course. Dynamically varying rule sets grant a packet classifier with very little time to examine or optimize the rule set database. A rule-set database is usually pre-processed and stored in optimal data structures for fast access. The pre-processing stage has a trade-off between time and memory consumption. Good optimizations can result from highly compressing the rule-set, but take a long time. Moreover, the faster the packet arrivals, the shorter the time the packet classifier has to classify a single packet.
An example of a multiple-field packet classification is a firewall. Firewalls usually have a small set of rules based on the policy of an organization. Firewall rules are quite general in terms of the number of kinds of packets it describes. The more general a rule, the larger the number of packets that match it. For example, a more general rule would have fewer fields per rule, and more wildcards or ranges for its fields. On the other hand, a more specific rule could have large number fields with each field represented by a singleton value. The generality of a rule has an implicit inverse relation with the cardinality and variation of the rule set.
Nonetheless, unlike firewalls, a flow-classifier table has a large set of rules with each rule spanning over many fields. A flow-classifier rule table is updated whenever a new flow is instantiated or an old flow is discarded. The frequency of flow creation or deletion is orders of magnitude higher than the rate of variation of a firewall table (i.e., firewall tables are updated when policies are revised).
Consequently, a system and method are needed to solve the above-identified problems and provide a simple, efficient and cost-effective way to classify packets in a dynamic environment.